ABC337 D -- Cheating Gomoku Narabe
ABC337 D -- Cheating Gomoku Narabe 問題
石oxがマス目内に0, 1個置かれた$ H行$ W列の盤面がある。 空白の場合.で表す。
さらに空白のマスにoを0個以上おくことで$ K個以上の縦の並び・横の並びを作ることができるかを判定せよ。 思いついた方針
幅1、高さ$ Kのフレームを1列の中で移動させる。
「フレーム」はoの並びを作れる場所を列挙する役割を持つ。
一マス下へ下へフレームを動かす。
動かすと同時に、フレーム内にあるoの数を数える。
$ O(K)かかるように見えて、実際には$ O(1)で済む。
oと.しかそのフレーム内になかったときに限り、そこで縦横の並びを作ることができる。
縦横の並びを作れる時で、かつoのフレーム内の個数が最大値を取るようなフレームの位置を探る
これを各々の行に対しても行えばよい。
こうすることで、フレームはすべての配置できうるoの並びを列挙できたことになる。
必要条件：求める並びはマス目がK個連続に並ぶものだけである。
$ \because 「求める並びならばマス目がK個連続に並ぶもの」の対偶
o.しか含まれないK個の並びでは実現できる。
xが1個でも含まれるK個の並びでは実現不可能。
1. フレーム内に含まれるoの最大値を探す。
2. if 列に幅1高さKのフレームが入り切る
2-1. for 列C in すべての列:
列Cのうち上のK個にあるo.の個数を数える。
for セルc in 列Cの上K個以外のマス目ら:
cの中身に応じて、oか.かいずれかの個数カウントを増やす
// フレームに入っていくセル
cよりK+1個上のセルの中身に応じて、oか.かいずれかの個数カウントを減らす
// フレームに出ていくセル
if もしフレーム内がoか.しかない:
現状のoの個数の最大値と比較して、更新する
3. if 行に幅K高さ1のフレームが入り切る
3-1. 行についても同様
4. フレーム内に含まれるoの最大値に基づいて、解を出力する。
列Cのうち上のK個にフレームを当てはめたときoの個数が最大値をとるようなケースで、最大値を捉えることができない。
ここが問題
2-1. for 列C in すべての列:
列Cのうち上のK個にあるo.の個数を数える。
!! <--- ここでも最大値チェックをする必要がある。
for セルc in 列Cの上K個以外のマス目ら:
cの中身に応じて、oか.かいずれかの個数カウントを増やす
// フレームに入っていくセル
....
被害
（得点ロス）
どう気づけばよかったか？
実際の道筋
次のテストケースを実行するとバグることに気づいた（終了3分前）
code:txt
4 4 4
oooo
xxxx
...x
結果として-1が帰ってくる。（バグ）
しかし、これは偶発的で神頼みな解決法
もう少しちゃんと理論立って指摘できないだろうか...？
基本的には最も手軽
1. フレーム内に含まれるoの最大値を探す。
2. if 列に幅1高さKのフレームが入り切る
2-1. for 列C in すべての列:
列Cのうち上のK個にあるo.の個数を数える。
if もしフレーム内がoか.しかない:
現状のoの個数の最大値と比較して、更新する
for セルc in 列Cの上K個以外のマス目ら:
cの中身に応じて、oか.かいずれかの個数カウントを増やす
// フレームに入っていくセル
cよりK+1個上のセルの中身に応じて、oか.かいずれかの個数カウントを減らす
// フレームに出ていくセル
if もしフレーム内がoか.しかない:
現状のoの個数の最大値と比較して、更新する
3. if 行に幅K高さ1のフレームが入り切る
3-1. 行についても同様
4. フレーム内に含まれるoの最大値に基づいて、解を出力する。
code:cpp
using Grid = std::vector<std::string>;
using Point = std::pair<int32_t, int32_t>;
int32_t H, W, K;
// フレーム内にグリッドの位置pのマス目が入ってきたときに、oの個数と.の個数をpのマス目の内容に応じて増大させる。
void increase_on(Grid& grid, const Point p, int& count_of_circle, int& count_of_dot);
// フレーム内にグリッドの位置pのマス目が出ていくときに、oの個数と.の個数をpのマス目の内容に応じて減少させる。
void decrease_on(Grid& grid, const Point p, int& count_of_circle, int& count_of_dot);
int main(){
std::cin >> H >> W >> K;
std::vector<std::string> grid(H);
for (int32_t i = 0; i < H; i++) {
}
// 各々の場所に幅1長さKのフレームを当てはめていく。
// ループ中、長さKのフレームの中を占めるoで最大だったもの
int32_t significant_count_of_circle = -1;
if (K <= W) {
for (int32_t r = 0; r < H; r++) {
int32_t count_of_dot = 0;
int32_t count_of_circle = 0;
for (int32_t c = 0; c < K; c++) {
increase_on(grid, {r, c}, count_of_circle, count_of_dot);
}
if (count_of_circle + count_of_dot == K) {
significant_count_of_circle = std::max(significant_count_of_circle, count_of_circle);
}
for (int32_t c = K; c < W; c++) {
// フレームから出ていく記号
decrease_on(grid, {r, c - K}, count_of_circle, count_of_dot);
// フレームに入ってくる記号
increase_on(grid, {r, c}, count_of_circle, count_of_dot);
// フレーム内でK目並べを作れるとき
if (count_of_circle + count_of_dot == K) {
significant_count_of_circle = std::max(significant_count_of_circle, count_of_circle);
}
}
}
}
if (K <= H) {
for (int32_t c = 0; c < W; c++) {
int32_t count_of_dot = 0;
int32_t count_of_circle = 0;
for (int32_t r = 0; r < K; r++) {
increase_on(grid, {r, c}, count_of_circle, count_of_dot);
}
if (count_of_circle + count_of_dot == K) {
significant_count_of_circle = std::max(significant_count_of_circle, count_of_circle);
}
for (int32_t r = K; r < H; r++) {
decrease_on(grid, {r - K, c}, count_of_circle, count_of_dot);
increase_on(grid, {r, c}, count_of_circle, count_of_dot);
if (count_of_circle + count_of_dot == K) {
significant_count_of_circle = std::max(significant_count_of_circle, count_of_circle);
}
}
}
}
std::cout << ((significant_count_of_circle == -1) ? -1 : K - significant_count_of_circle) << std::endl;
return 0;
}